﻿#pragma once
#include "Index.h"

/**
 * 0~n-1中缺失的数字.
 * https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/
 *
 * 一个长度为n-1的递增排序数组中所有的数字都是唯一的,并且每个数字都在范围0~n-1之内.
 * 在范围0~n-1的n个数字中有且只有一个数字不在该数组中,请找出这个数字.
 */
namespace FindLackedNum
{
	class Question {
	public:
		virtual int takeAttendance(std::vector<int>& records) =0;
	};

	class AllSum :public Question
	{
	public:
		int takeAttendance(std::vector<int>& records) override
		{
			int sum= std::accumulate(records.begin(), records.end(), 0);

			int n = records.size();
			int totalSum = n * (n + 1) / 2;
			return totalSum - sum;
		}
	};

	class Binary:public Question
	{
	public:
		//找递增排序数组中第一个和下标不匹配的值
		int takeAttendance(std::vector<int>& records) override
		{
			if (records.empty())
				return -1;

			//二分左右边界
			int left = 0;
			int right = records.size() - 1;

			//第一个出现下标和值不符合的位置
			int mismatch = -1;
			while(left<=right)
			{
				int mid = left + ((right - left) >> 1);

				if (records[mid] == mid)
					left = mid + 1;
				else
				{
					mismatch = mid;
					right = mid - 1;
				}
			}

			if (mismatch >= 0)
				return mismatch - 1;//有出现下标不匹配的位置,前一个就是缺失的数字
			else
				return records.back() + 1;//缺失的是最后的数,如输入"[0,1,2]"缺失的是3
		}
	};

	class Practice:public Question
	{
	public:
		//使用二分法找到首个位置i,满足 records[i]>i
		int takeAttendance(std::vector<int>& records) override
		{
			if(records.empty())
				throw "no answer";

			//可能缺失的位置在末尾,如 [0,1,2]缺了"3"
			int ans=records.size();

			int left=0,right=records.size()-1;
			while(left <= right)
			{
				const int mid=left+((right-left)>>1);
				if(records[mid]>mid)
				{
					ans=mid;
					right=mid-1;
				}
				else
				{
					left=mid+1;
				}
			}

			return ans;
		}
	};

	TEST(LackedNumTest,find)
	{
		TEST_SOLUTION1(Question, Practice, &)
		{
			__slnTestor.setTestTimes(100);
			int n = TestingUtil::randIntBetween(400, 600);
			int miss = static_cast<int>(n * TestingUtil::randFloatIn01());

			std::vector<int> nums(n - 1, 0);
			for (int i = 0; i < miss; ++i)
				nums[i] = i;
			for (int i = miss; i < n - 1; ++i)
				nums[i] = i + 1;
			int findMiss= solution->takeAttendance(nums);
			EXPECT_EQ(findMiss, miss);
		};
	}

	TEST(LackedNumTest, find_lackFirst)
	{
		TEST_SOLUTION1(Question,Practice, &)
		{
			auto nums= TestingUtil::parseNums<int>("[1,2,3]");
			int miss = 0;
			int findMiss= solution->takeAttendance(nums);
			EXPECT_EQ(findMiss, miss);
		};
	}

	TEST(LackedNumTest, find_lackLast)
	{
		TEST_SOLUTION1(Question, Practice, &)
		{
			auto nums = TestingUtil::parseNums<int>("[0,1,2]");
			int miss = 3;
			int findMiss = solution->takeAttendance(nums);
			EXPECT_EQ(findMiss, miss);
		};
	}
}